from RandomList import GetRandomList

# 二重选择排序：每次不仅找最小的还找最大的
def double_selection_sort(arr):
    left_idx = 0
    right_idx = len(arr) - 1
    cur_min_idx = cur_max_idx = 0
    cur_min = cur_max = 0
    while left_idx < right_idx:
        if arr[left_idx] <= arr[right_idx]:
            cur_min_idx = left_idx
            cur_max_idx = right_idx
            cur_min = arr[left_idx]
            cur_max = arr[right_idx]
        else:
            cur_min_idx = right_idx
            cur_max_idx = left_idx
            cur_min = arr[right_idx]
            cur_max = arr[left_idx]

        for i in range(left_idx + 1, right_idx - 1):
            if cur_min > arr[i]:
                cur_min_idx = i
            if cur_max < arr[i]:
                cur_max_idx = i
            cur_max = arr[cur_max_idx]
            cur_min = arr[cur_min_idx]
        arr[cur_max_idx], arr[right_idx] = arr[right_idx], arr[cur_max_idx]
        arr[cur_min_idx], arr[left_idx] = arr[left_idx], arr[cur_min_idx]
        left_idx += 1
        right_idx -= 1
    return arr

            
if __name__ == "__main__":
    Arr = GetRandomList(100)
    Arr = double_selection_sort(Arr)
    print(Arr)